#include <iostream>
#include <vector>
#include <cstdlib>
#include <sys/time.h>
#include "PriorityQueue.h"

#define N 30
#define TEST 8
#define MAX 1000000
#define CALTIME (end.tv_sec - start.tv_sec) * 1000 + (end.tv_usec - start.tv_usec) / 1000
#define PRINT(B){\
    for( int i = 0; i < B.size(); i++ )\
        cout << B[i].data << " ";\
    cout << endl;\
    }
using namespace std;

/**
* @brief To calculate the average number of the array.
* 
* @param num, size
*/
int average(const int* num, const int size)
{
    int ave = 0;
    for (int i = 0; i < size; i++)
    {
    ave += num[i];
    }
    ave /= size;
    return ave;
}

int main()
{
    // 功能性测试，测试该库内函数可以正常运行。
    PriorityQueue<int, int> A, A2;
    vector<PriorityQueue<int, int>::DataBase> B;
    for( int i = 0; i <= N; i++ )
        B.push_back( {i+1, i+1} );
    cout << "Test for one DatBase." << endl;
    A.insert({0,0});
    cout << A.top() << endl;
    A.clear();
    PriorityQueue<int, int>::DataBase x = {-1,100};
    A.insert(x);
    A.print();
    cout << "Test for vector -> buildHeap." << endl;
    A.buildHeap( B );
    A.print();
    cout << "Test for deleteMin()." << endl;
    A.deleteMin();
    cout << "The top element change into : " << A.top() << endl;
    cout << "Print the rest vector if delete for more 5 times." << endl;
    for( int i = 0; i < 5; i++ )
        A.deleteMin();
    A.print();
    cout << "Test for remove. After removing 8:" << endl;
    A.remove(8);
    A.print();
    cout << "Removing from 10 - 20: " << endl;
    for( int i = 0; i <= 10 ; i++ )
        A.remove( i + 10 );
    A.print();
    cout << "Test for modify" << endl;
    cout << "23+10: "; 
    A.modifyData(23,10);
    A.print();
    cout << "9-10: ";
    A.modifyData(9,-10);
    A.print();
    cout << "Test for data not unique." << endl;
    A.buildHeap(B);
    A.print();
    A.clear();
    cout << "Test for random datas." << endl;
    B.clear();
    for( int i = 0; i < N; i++ )
        B.push_back({ i, rand() % 100 });
    PRINT(B);
    A.buildHeap(B);
    A.print();
    cout << "Test for merge." << endl;
    cout << "A : ";
    A.print();
    for( int i = 0; i < 10; i++ )
        A2.insert({ 100+i, rand() % 100 });
    cout << "A2 : ";
    A2.print();
    A.merge(A2);
    cout << "After merge two heal.";
    A.print();

    // 测试效率
    int Time[ TEST ];
    int ave;
    struct timeval start, end;
    vector<PriorityQueue<int, int>::DataBase> Store[ TEST ];
    for( int k = 0; k < TEST; k++ )
        for( int i = 0; i < MAX; i++ )
            Store[k].push_back({ k * MAX + i, rand() % MAX });
    int whole;
    // Test for insert
    cout << endl << "Test the efficiency of insert()." << endl;
    while( 1 )
    {
        cin >> whole;
        if( whole <= 0 )
            break;
        
        for( int k = 0; k < TEST; k++ )
        {
            A.clear();
            gettimeofday( & start, nullptr );
            for( int i = 0; i < whole; i++ )
                A.insert( Store[k][i] );
            gettimeofday( & end, nullptr );
            Time[ k ] = CALTIME;
        }
        ave = average( Time, TEST );
        cout << "Insert for " << whole << " numbers, average time is " << ave << "ms." << endl;
    }

    // Test for deleteMin
    cout << endl << "Test the efficiency of deleteMin()." << endl;
    while( 1 )
    {
        cin >> whole;
        if( whole <= 0 )
            break;
        
        for( int k = 0; k < TEST; k++ )
        {
            A.clear();
            for( int i = 0; i < whole; i++ )
                A.insert( Store[k][i] );
            gettimeofday( & start, nullptr );
            while( ! A.isEmpty() )
                A.deleteMin();
            gettimeofday( & end, nullptr );
            Time[ k ] = CALTIME;
        }
        ave = average( Time, TEST );
        cout << "DeleteMin for " << whole << " numbers, average time is " << ave << "ms." << endl;
    }

    // Test for buildHeap
    cout << endl << "Test the efficiency of buildHeap()." << endl;
    while( 1 )
    {
        cin >> whole;
        if( whole <= 0 )
            break;
        
        for( int k = 0; k < TEST; k++ )
        {
            vector<PriorityQueue<int, int>::DataBase> C;
            for( int j = 0; j < whole; j++ )
                C.push_back( Store[k][j] );
            A.clear();
            gettimeofday( & start, nullptr );
            A.buildHeap( C );
            gettimeofday( & end, nullptr );
            Time[ k ] = CALTIME;
            C.clear();
        }
        ave = average( Time, TEST );
        cout << "BuildHeap for " << whole << " numbers, average time is " << ave << "ms." << endl;
    }

    // Test for remove
    cout << endl << "Test the efficiency of remove()." << endl;
    while( 1 )
    {
        cin >> whole;
        if( whole <= 0 )
            break;
        
        for( int k = 0; k < TEST; k++ )
        {
            A.clear();
            for( int i = 0; i < whole; i++ )
                A.insert( Store[k][i] );
            gettimeofday( & start, nullptr );
            for( int j = 0; j < whole; j++ )
                A.remove( Store[k][j].key );
            gettimeofday( & end, nullptr );
            Time[ k ] = CALTIME;
        }
        ave = average( Time, TEST );
        cout << "Remove for " << whole << " numbers, average time is " << ave << "ms." << endl;
    }

    // Test for modifyData
    cout << endl << "Test the efficiency of modifyData()." << endl;
    while( 1 )
    {
        cin >> whole;
        if( whole <= 0 )
            break;
        
        for( int k = 0; k < TEST; k++ )
        {
            A.clear();
            for( int i = 0; i < whole; i++ )
                A.insert( Store[k][i] );
            gettimeofday( & start, nullptr );
            for( int j = 0; j < whole; j++ )
                A.modifyData( Store[k][j].key, j );
            gettimeofday( & end, nullptr );
            Time[ k ] = CALTIME;
        }
        ave = average( Time, TEST );
        cout << "ModefyData for " << whole << " numbers, average time is " << ave << "ms." << endl;
    }

    // Test for merge
    cout << endl << "Test the efficiency of merge()." << endl;
    while( 1 )
    {
        cin >> whole;
        if( whole <= 0 )
            break;
        
        for( int k = 0; k < TEST; k++ )
        {
            A.clear();
            A2.clear();
            for( int i = 0; i < whole; i++ )
                A.insert( Store[k][i] );
            int k2 = ( k == 0 ) ? TEST-1 : k-1;
            for( int i = 0; i < whole; i++ )
                A2.insert( Store[k2][i] );
            gettimeofday( & start, nullptr );
                A.merge( A2 );
            gettimeofday( & end, nullptr );
            Time[ k ] = (end.tv_sec - start.tv_sec) * 1000000 + end.tv_usec - start.tv_usec;
        }
        ave = average( Time, TEST );
        cout << "Merge for two vector of " << whole << " numbers, average time is " << ave << "ms." << endl;
    }

    return 0;
}